% Theoretische Informatik und Logik ue2
% 2 November 2020

# Aufgabe 2.1

## (a)

$$
\begin{aligned}
G_1 &= \langle \{ S, D, W \}, \{ \underline a, \underline b, \underline c, \underline d \}, P_1, S \rangle \\
P_1 &= \{ S \rightarrow D \mid \varepsilon, D \rightarrow WD \underline d \mid W \underline d, W \rightarrow \underline a \underline b \underline c \}
\end{aligned}
$$

Die Linksableitung für $w_1 = aabbdddd \in L_1$ sieht dann wie folgt aus:

$$
\begin{aligned}
S
&\Rightarrow_L D
\Rightarrow_L aDd
\Rightarrow_L aWDdd
\Rightarrow_L aaDdd
\Rightarrow_L aaWDddd \\
&\Rightarrow_L aabDddd
\Rightarrow_L aabWdddd
\Rightarrow_L aabbdddd
\end{aligned}
$$

Folgender Ableitungsbaum ergibt sich für $w_1$:

![](./res/2-1-a.png){ width=30% }

## (b)

$$
\begin{aligned}
L_2 = \{ a^n b^{2k} a^n \mid k, n \geq 0 \} \\
G_2 &= \langle \{ S, A, B \}, \{ \underline a, \underline b \}, P_2, S \rangle \\
P_2 &= \{ S \rightarrow A \mid \varepsilon, A \rightarrow B \mid \underline a A \underline a \mid \underline {aa}, B \rightarrow \underline b B \underline b \mid \underline b \underline b \}
\end{aligned}
$$

Die Linksableitung für $w_2 = aabbbbaa \in L_2$ sieht dann wie folgt aus:

$$
\begin{aligned}
S
&\Rightarrow_L A
\Rightarrow_L aAa
\Rightarrow_L aaAaa
\Rightarrow_L aaBaa
\Rightarrow_L aabBbaa
\Rightarrow_L aabbbbaa
\end{aligned}
$$

Folgender Ableitungsbaum ergibt sich für $w_2$:

![](./res/2-1-b.png){ width=30% }

## (c)

$$
\begin{aligned}
G_3 &= \langle \{ S, C \}, \{ \underline a, \underline b, \underline c \}, P_3, S \rangle \\
P_3 &= \{ S \rightarrow C \mid CC \mid \varepsilon, C \rightarrow \underline {ab} C \underline c \mid \underline {abc} \}
\end{aligned}
$$

Die Linksableitung für $w_3 = abababcccabc \in L_3$ sieht dann wie folgt aus:

$$
\begin{aligned}
S
&\Rightarrow_L CC
\Rightarrow_L abCcC
\Rightarrow_L ababCccC
\Rightarrow_L abababcccC
\Rightarrow_L abababcccabc
\end{aligned}
$$

Folgender Ableitungsbaum ergibt sich für $w_3$:

![](./res/2-1-c.png){ width=30% }

# Aufgabe 2.2

## (a)

Die Sprache ist kontextfrei. Hier lässt sich eine entsprechender Homomorphismus angeben:

![](./res/2-2-a.png){ width=50% }

## (b)

Die Sprache ist kontextfrei. Betrachten wir zunächst eine Grammatik, welche die gegebene Sprache erzeugen würde. Alle voneinander unterschiedlichen Situationen (entsprechen den Produktionsregeln) benötigen nun ihre eigene Definition als Klammerpaar. Beispielsweise kann für einen Klammerausdruck die öffnende Klammer aus `bb` bestehen, und die dazugehörige schließende Klammer `a`. Gleichzeitig brauchen wir aber ein anderes Klammernpaar für `abb` (analog für weitere Kombinationen).

![](./res/2-2-b.png){ width=50% }

Ein paar Beispiele illustrieren wie sich vorgehen lässt:

![](./res/2-2-b-ex.png){ width=50% }

## (c)

![](./res/2-2-c.png){ width=50% }

## (d)

$$
L_4 = \{ (\underline{ab})^{3k} \underline c^{6k} (\underline de)^{3k} \underline f^{12k} \mid k \geq 0 \} = \{ (\underline{ab})^{3k} (\underline{cc})^{3k} (\underline{de})^{3k} (\underline{ffff})^{3k} \mid k \geq 0 \}
$$

ist *nicht* kontextfrei!

$L_4$ entspricht $\{ \underline 0^{nk_2} \underline 1^{nl} \underline 2^{mn} \mid n \geq 0 \}$ mit $k_2 = 2 \cdot 3, l = m = 4 \cdot 3$ durch:

$$
h : \{ \underline a, \underline b, \underline c, \underline d, \underline e, \underline f \}^* \rightarrow \{ \underline 0, \underline 1, \underline 2 \}^*
$$

$h(\underline a) = \underline 0; h(\underline b) = \underline 0; h(\underline c) = \underline 1; h(\underline d) = \underline 1; h(\underline e) = \underline 1; h(\underline f) = \underline 2$

# Aufgabe 2.3

## (a)

Nein.

Nicht für inherent mehrdeutige Sprachen.

## (b)

Nein.

$\Sigma^* \in \mathcal{L}_1$ hat das Komplement $\{\}$, welches endlich ist.

## (c)

Nein, nicht allgemein.

$$
A - B = A \cap \overline B
$$

Da $B$ gegenüber dem Komplement abgeschlossen sein muss, muss $B$ rekursiv sein. Daher ist $A - B$ nur rekursiv aufzählbar, wenn $B$ rekursiv ist.

## (d)

Nein.

$\mathcal{L}_3 \subset \mathcal{L}_2$, es existieren also Sprachen die von einem Kellerautomaten akzeptiert werden, aber für welche es keine reguläre Grammatik gibt.

## (e)

Ja.

Betrachte $\{\}$.

## (f)

Nein.

$L = \{\} = \mathcal{L}(G)$ ist entscheidbar.

# Aufgabe 2.4

## (a)

Nein.

Aus $P \not = NP$ würde folgen, dass $P \subset NP$. Somit liegt aber jedes Problem aus $P$ in $NP$.

## (b)

Ja.

Da jedes $NP$-vollständiges Problem entscheidbar ist (wird von einer Turing Maschine akzeptiert), so muss auch das komplement jedes $NP$-vollständigen Problems entscheidbar sein.

## (c)

Nein.

Aus $\exists \ l \in NP$-hart$:\ l \not \in NP$ folgt, dass dann nicht alle Probleme in $NP$-hart automatisch in polynomiell beschränkter Zeit lösbar wären.

## (d)

Nein.

Wir wissen dann, dass $A$ in $NP$-hart liegt. Aber da wir nicht wissen ob $B$ in $NP$ liegt, können wir keine Aussage darüber treffen, ob $A$ in $NP$ liegt.

## (e)

Ja.

Ist das Komplement von $B$ endlich, so gilt $\overline B \in \mathcal{L}_3$. Gleichzeitig gilt deswegen aber $B \in \mathcal{L}_3$. Für jede reguläre Sprache können wir einen deterministischen endlichen Automaten finden die ein Wort in $O(n)$ Zeit entscheiden kann, somit ist $B$ in polynomieller Zeit lösbar. In Folge ist dann auch $A$ in polynomieller Zeit lösbar.

## (f)

Keine Aussage möglich.

Die Antwort hängt davon ab, ob $NP$ abgeschlossen unter dem Komplement ist. Das ist der Fall wenn $P = NP$, da $P$ unter dem Komplement abgeschlossen ist. Im Umkehrschluss ist das nicht der Fall wenn $P \not = NP$.

# Aufgabe 2.5

Gegeben ist $\alpha$ in DNF und gefragt ist Widerlegbarkeit. Wird $\alpha$ negiert, so werden $\land$ und $\lor$ Operatoren vertauscht und alle Variablen negiert. Wir nennen diesen neuen Term $\beta$, daher $\neg \alpha = \beta$. Die Frage, ob $\alpha$ widerlegbar ist, entspricht nun der Frage, ob $\beta$ erfüllbar ist. Eine Probleminstanz $\alpha$ unseres Problems entspricht also einer Probleminstanz $\beta$ des Problems SAT.

Nun müssen wir zeigen, dass es auch eine polynomielle Reduktion von SAT auf unser Problem gibt. Dafür wenden wir denselben Trick an, wir nehmen unsere Probleminstanz $\beta$ und formen ihn um, enstprechend der Relation $\neg \alpha = \beta \implies \alpha = \neg \beta$. Angenommen es gibt insgesamt $n$ Variablen und $k$ Klauseln zu $l$ Variablen pro Klausel als obere Schranken, dann müssen zur Umformung einer KNF zu einer DNF höchstens $k - 1$ "$\land$" Symbole, $k \cdot (l - 1)$ "$\lor$" Symbole und $n \cdot l$ Variablen ausgetauscht werden. Unser Problem ist somit reduzierbar in $O(k - 1 + k \cdot (l - 1) + n \cdot l) = O(k + k \cdot l - k + n \cdot l) = O(l \cdot (n + k))$ und daher in polynomieller Zeit reduzierbar.

Da $SAT \leq_P W$, wobei $W$ unser Problem sei, und $SAT$ $NP$-vollständig ist, ist $W$ auch $NP$-vollständig. Wir wissen das $NP$-vollständige Probleme gleichzeitig $NP$-hart sind, daher ist $W$ $NP$-hart.
